package leetcode100

// TODO 递归 [两种经典递归 | 全局变量递归] 【-】 二叉树的最大深度
// TODO https://leetcode.cn/problems/maximum-depth-of-binary-tree/solution/kan-wan-zhe-ge-shi-pin-rang-ni-dui-di-gu-44uz/

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    lDepth := maxDepth(root.Left)
    rDepth := maxDepth(root.Right)
    return max(lDepth, rDepth) + 1
}

func max(a, b int) int { if b > a { return b }; return a }

func maxDepth2(root *TreeNode) (ans int) {
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, cnt int) {
        if node == nil {
            return
        }
        cnt++
        ans = max(ans, cnt)
        dfs(node.Left, cnt)
        dfs(node.Right, cnt)
    }
    dfs(root, 0)
    return
}